package test.zj;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * @Description
 * @Author Firenut
 * @Date 2023-08-21 23:48
 */
public class T210_findOrder {
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        // List<Integer> res = new ArrayList<>();
        int[] ans = new int[numCourses];
        List<List<Integer>> grip = new ArrayList<>();
        int[] du = new int[numCourses];

        // 初始化邻接表
        for (int i = 0; i < prerequisites.length; i++) {
            grip.add(new ArrayList<>());
        }

        for (int i = 0; i < prerequisites.length; i++) {
            int a = prerequisites[i][1];
            int b = prerequisites[i][0];
            grip.get(a).add(b);
            du[b]++;
        }

        LinkedList<Integer> queue = new LinkedList<>();
        for (int i = 0; i < du.length; i++) {
            if (du[i] == 0) {
                queue.add(i);
            }
        }

        int count = 0;
        while (!queue.isEmpty()) {
            int v = queue.removeFirst();
            ans[count++] = v;
            // res.add(v);
            for (int i : grip.get(v)) {
                du[i]--;
                if (du[i] == 0) {
                    queue.addLast(i);
                }
            }
        }

        if (count == numCourses) {
            return ans;
        }
        return new int[0];
    }
}
